#include<bits/stdc++.h>
using namespace std;
long long T,x,n,l,sm,ans,v[500009],s[500009],t[500009];
priority_queue<long long> p,q;
map<long long,int> f;
int main(){
    freopen("kte.in","r",stdin);
    freopen("kte.out","w",stdout);
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&x);
        if(f[x]==1){
            f[x]=0;
            sm-=x;
            n--;
        }
        else{
            f[x]=1;
            sm+=x;
            n++;
        }
        if(f[x]){
            for(int i=n;i;i--){
                if(v[i-1]>x)v[i]=v[i-1];
                else {
                    v[i]=x;
                    break;
                }
            }
        }
        else{
            l=lower_bound(v+1,v+n+2,x)-v;
            for(int i=l;i<=n;i++){
                if(v[i]>=x)v[i]=v[i+1];
            }
        }
        for(int i=1;i<=n;i++){
            s[i]=s[i-1]+v[i];
        }
        ans=0;
        for(int i=1;i<=n;i++){
            if(i<=n-i+1&&s[i]+s[n-i+1]>sm){
                if(i!=n-i+1)ans+=(s[i]-sm+s[n-i+1])<<1;
                else ans+=s[i]-sm+s[n-i+1];
            }
            else break;
        }
        printf("%lld\n",sm-ans);
    }
    return 0;
}
